Universality in Numerical Computations with Random Data. Case Studies

摘要

The authors present evidence for universality in numerical computations withrandom data. Given a (possibly stochastic) numerical algorithm with randominput data, the time (or number of iterations) to convergence (within a giventolerance) is a random variable, called the halting time. Two-componentuniversality is observed for the fluctuations of the halting time, i.e., thehistogram for the halting times, centered by the sample average and scaled bythe sample variance, collapses to a universal curve, independent of the inputdata distribution, as the dimension increases. Thus, up to two components, thesample average and the sample variance, the statistics for the halting time areuniversally prescribed. The case studies include six standard numericalalgorithms, as well as a model of neural computation and decision making. Alink to relevant software is provided in for the reader who would like to docomputations of his'r own.